763. 划分字母区间

Similar Question

Solution Tips

方案一: 区间思路 (贪心)

var partitionLabels = function(s) {
    // 感觉是哈希表呀
    // 先根据字母统计出区间, 然后按照区间进行划分
    // 将重叠的区间合并为一个
    // 记录是否出现过, 以及对应的 index
    const map = {};
    // 根据出现的 order, push 区间
    const order = [];
    for (let i = 0; i < s.length; i++) {
        // 不能按照字母表排序, 要按照出现的顺序排序
        // 字符串好像就是插入顺序来的?
        // 不是, 字符串属性也是字典序的, 那就一边插入一遍排序
        const charCode = s[i];
        if (map[charCode] === undefined) {
            order.push([i]);
            map[charCode] = order.length - 1;
        }
        else {
            const o = map[charCode];
            order[o].push(i);
        }
    }
    // 记录 maxRight, 将所有 right 小于 maxRight 的都归为一组
    let start = 0;
    let maxRight = 0;
    let partLen = 0;
    const res = [];
    for (const list of order) {
        const l = list[0];
        const r = list[list.length - 1];

        if (maxRight >= l) {
            // 两个字母的区间有重叠, 只能合并到一起 part
            // 更新maxRight
            maxRight = Math.max(maxRight, r);
            partLen = maxRight - start + 1;
        }
        else {
            // 一个新的区间
            res.push(partLen);
            start = l;
            maxRight = r;
            partLen = maxRight - start + 1;
        }
    }
    // 最后一个区间
    partLen > 0 && res.push(partLen);

    return res;

};
console.log(partitionLabels(""))

方案二: 跳跃思路 (贪心)

只关心右边就够了, 到达了 maxRight 自然就是新区间, 所以不需要 start 和 l 变量

相当于是跳跃思路, 每次跳跃到能跳到最远的地方

var partitionLabels = function(s) {
    const last = new Array(26);
    const length = s.length;
    const codePointA = 'a'.codePointAt(0);
    for (let i = 0; i < length; i++) {
        last[s.codePointAt(i) - codePointA] = i;
    }
    const partition = [];
    let start = 0, end = 0;
    for (let i = 0; i < length; i++) {
        end = Math.max(end, last[s.codePointAt(i) - codePointA]);
        if (i == end) {
            partition.push(end - start + 1);
            start = end + 1;
        }
    }
    return partition;
};